/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
#ifndef __STD_ALGORITHM_H_VERSION_KL__
#define __STD_ALGORITHM_H_VERSION_KL__

#include "buffer.h"
#include "numeric.h"
#include "sort.h"

KL_BEGIN
// FUNCTION adjacent_difference {
template<typename InIter, typename OutIter>
inline OutIter adjacent_difference(InIter first, InIter last, OutIter dest)
{
	if(first == last) return dest;
	typename iterator_traits<InIter>::type value = *first;
	*dest = value;
	for(++dest; ++first != last; ++dest)
	{
		typename iterator_traits<InIter>::type temp = *first;
		*dest = temp - value;
		value = temp;
	}
	return dest;
}
template<typename InIter, typename OutIter, typename Minus>
inline OutIter adjacent_difference(InIter first, InIter last,
								   OutIter dest, Minus fun)
{
	if(first == last) return dest;
	typename iterator_traits<InIter>::type value = *first;
	*dest = value;
	for(++dest; ++first != last; ++dest)
	{
		typename iterator_traits<InIter>::type temp = *first;
		*dest = fun(temp, value);
		value = temp;
	}
	return dest;
}
// FUNCTION adjacent_difference }
// FUNCTION adjacent_find {
template<typename InIter>
inline InIter adjacent_find(InIter first, InIter last)
{
	return adjacent_find(first, last, 
		KL::equal_to<iterator_traits<InIter>::type>()); 
}
template<typename InIter, typename Equal>
inline InIter adjacent_find(InIter first, InIter last, Equal fun)
{
	if(first == last) return last;
	InIter temp = first;
	while(++first != last)
	{
		if(fun(*temp, *first)) return temp;
		temp = first;
	}
	return last;
}
// FUNCTION adjacent_find }
// FUNCTION binary_search {
template<typename RanIter, typename Value>
inline bool binary_search(RanIter const &first, RanIter const &last,
						  Value const &value)
{
	RanIter result = lower_bound(first, last, value);
	return (result != last && !(value < *result));
}
template<typename RanIter, typename Value, typename Less>
inline bool binary_search(RanIter const &first, RanIter const &last, 
						  Value const &value, Less fun)
{
	RanIter result = lower_bound(first, last, value, fun);
	return (result != last && !fun(value, *result));
}
// FUNCTION binary_search }
// FUNCTION lower_bound {
template<typename RanIter, typename Value, typename Less>
inline RanIter lower_bound(RanIter first, RanIter last, Value const &value, Less fun)
{
	size_t count = KL::distance(first, last);
	while(count)
	{
		size_t mid_pos = count / 2;
		RanIter middle = first + mid_pos;
		if(fun(*middle, value)) first = ++middle, count -= mid_pos + 1;
		else last = middle, count = mid_pos;
	}
	return first;
}
template<typename RanIter, typename Value>
inline RanIter lower_bound(RanIter first, RanIter last, Value const &value)
{
	return lower_bound(first, last, value, 
		KL::less2<iterator_traits<RanIter>::type, Value>());
}
// FUNCTION lower_bound }
// FUNCTION upper_bound {
template<typename RanIter, typename Value, typename Less>
inline RanIter upper_bound(RanIter first, RanIter last, Value const &value, Less fun)
{
	size_t count = KL::distance(first, last);
	while(count)
	{
		size_t mid_pos = count / 2;
		RanIter middle = first + mid_pos;
		if(fun(value, *middle)) last = middle, count = mid_pos;
		else first = ++middle, count -= mid_pos + 1;
	}
	return first;
}
template<typename RanIter, typename Value>
inline RanIter upper_bound(RanIter first, RanIter last, Value const &value)
{
	return upper_bound(first, last, value, 
		KL::less2<iterator_traits<RanIter>::type, Value>());
}
// FUNCTION upper_bound }
// FUNCTION copy, copy_n, copy_backward {
template<class InIter, class OutIter>
inline OutIter copy(InIter const &first, InIter const &last, OutIter const &dest)
{
	return KL::_memory_helper_<iterator_traits<InIter>::value_type>
		::copy(first, last, dest);
}
template<class InIter, class OutIter>
inline OutIter copy_n(InIter const &first, size_t num, OutIter const &dest)
{	
	return KL::_memory_helper_<iterator_traits<InIter>::value_type>
		::copy_n(first, num, dest);
}
template<class InIter, class OutIter>
inline OutIter copy_backward(InIter const &first, InIter const &last, 
							 OutIter const &dest_last)
{	
	return KL::_memory_helper_<iterator_traits<InIter>::value_type>
		::copy_backward(first, last, dest_last);
}
// FUNCTION copy, copy_n, copy_backward }
// FUNCTION count, count_if {
template<class InIter, class Value>
inline size_t count(InIter first, InIter last, Value const &value)
{
	size_t num = 0;
	for(; first != last; ++first)
	{
		if(value == *first) ++num;
	}
	return num;
}
template<class InIter, class Bool>
inline size_t count_if(InIter first, InIter last, Bool fun)
{
	size_t num = 0;
	for(; first != last; ++first)
	{
		if(fun(*first)) ++num;
	}
	return num;
}
// FUNCTION count, count_if }
// FUNCTION equal_range {
template<typename RanIter, typename Value>
static KL::pair<RanIter, RanIter> 
equal_range(RanIter first, RanIter last, Value const &value)
{
	return equal_range(first, last, value, 
		KL::less2<iterator_traits<RanIter>::type, Value>());
}
template<typename RanIter, typename Value, typename Less>
static KL::pair<RanIter, RanIter> 
equal_range(RanIter first, RanIter last, Value const &value, Less fun)
{		
	size_t count = KL::distance(first, last);
	while(count)
	{
		size_t mid_pos = count / 2;
		RanIter middle = first + mid_pos;
		if(fun(*middle, value)) first = ++middle, count -= mid_pos + 1;
		else if(fun(value, *middle)) last = middle, count = mid_pos; 
		else
		{
			return KL::make_pair(lower_bound(first, middle, value, fun),
				upper_bound(middle, last, value, fun));
		}
	}
	return KL::make_pair(first, first);
}
// FUNCTION equal_range }
// FUNCTION equal {
template<class InIterL, class InIterR>
inline bool equal(InIterL first0, InIterL last0, InIterR first)
{
	for(; first0 != last0 && *first0 == *first; ++first0, ++first);
	return first0 == last0;
}
template<class InIterL, class InIterR, class Equal>
inline bool equal(InIterL first0, InIterL last0, InIterR first, Equal fun)
{
	for(; first0 != last0 && fun(*first0, *first); ++first0, ++first);
	return first0 == last0;
}
// FUNCTION equal }
// FUNCTION fill, fill_n {
template<typename OutIter, typename Value>
void fill(OutIter first, OutIter last, Value const &value)
{
	for(; first != last; ++first) *first = value;
}
template<typename OutIter, typename Value>
void fill_n(OutIter first, size_t num, Value const &value)
{
	for(; num--; ++first) *first = value;
}
// FUNCTION fill, fill_n }
// FUNCTION find, find_end, find_if, find_first_of {
template<typename InIter, typename Value>
inline InIter find(InIter first, InIter last, Value const &value)
{
	for(; first != last && *first != value; ++first);
	return first;
}
template<typename InIterSrc, typename InIterDest>
inline InIterSrc find_end(InIterSrc first0, InIterSrc last0, 
						  InIterDest first, InIterDest last)
{
	return search_end(first0, last0, first, last);
}
template<typename InIterSrc, typename InIterDest, typename Equal>
inline InIterSrc find_end(InIterSrc first0, InIterSrc last0, 
						  InIterDest first, InIterDest last, Equal fun)
{
	return search_end(first0, last0, first, last, fun);
}
template<typename InIter, typename Func1>
inline InIter find_if(InIter first, InIter last, Func1 fun)
{
	for(; first != last && !fun(*first); ++first);
	return first;
}
template<typename InIterSrc, typename InIterDest>
inline InIterSrc find_first_of(InIterSrc first0, InIterSrc last0, 
							   InIterDest first, InIterDest last)
{
	for(; first0 != last0; ++first0)
	{
		InIterDest head = first;
		typedef typename KL::iterator_traits<InIterSrc>::type type;
		type &value = *first0;
		for(; head != last; ++head)
		{
			if(value == *head) return first0;
		}
	}
	return last0;
}
// FUNCTION find, find_end, find_if, find_first_of }
// FUNCTION foreach {
template<typename InIter, typename Func1>
inline Func1 foreach(InIter first, InIter last, Func1 fun)
{
	for(; first != last; ++first) fun(*first);
	return fun;
}
// FUNCTION foreach }
// FUNCTION generate, generate_n {
template<typename OutIter, typename Func0>
inline void generate(OutIter first, OutIter last, Func0 fun)
{
	for(; first != last; ++first) *first = fun();
}
template<typename OutIter, typename Func0>
inline OutIter generate_n(OutIter first, size_t num, Func0 fun)
{
	for(; num--; ++first) *first = fun();
	return first;
}
// FUNCTION generate, generate_n }
// FUNCTION includes {
template<typename InIterL, typename InIterR>
inline bool includes(InIterL first0, InIterL last0,
					 InIterR first, InIterR last)
{
	for(; first != last; ++first)
	{
		for(; first0 != last0 && *first0 < *first; ++first0);
		if(first0 == last0 || *first < *first0) return false;
	}
	return true;
}
template<typename InIterL, typename InIterR, typename Less>
inline bool includes(InIterL first0, InIterL last0,
					 InIterR first, InIterR last, Less fun)
{
	for(; first != last; ++first)
	{
		for(; first0 != last0 && less(*first0, *first); ++first0);
		if(first0 == last0 || less(*first, *first0)) return false;
	}
	return true;
}
// FUNCTION includes }
// FUNCTION is_sorted {
template<typename InIter>
inline bool is_sorted(InIter first, InIter last)
{
	if(first == last) return true;
	InIter temp = first;
	while(++first != last)
	{
		if(*first < *temp) return false;
		temp = first;
	}
	return true;
}
template<typename InIter, typename Less>
inline bool is_sorted(InIter first, InIter last, Less fun)
{
	if(first == last) return true;
	InIter temp = first;
	while(++first != last)
	{
		if(fun(*first, *temp)) return false;
		temp = first;
	}
	return true;
}
// FUNCTION is_sorted }
// FUNCTION iter_swap {
template<typename AddressL, typename AddressR>
inline void iter_swap(AddressL left, AddressR right)
{
	KL::swap(*left, *right);
}
// FUNCTION iter_swap }
// FUNCTION lexicographical_compare lexicographical_compare_3way{
template<typename InIterL, typename InIterR>
inline bool lexicographical_compare(InIterL first0, InIterL last0, 
									InIterR first, InIterR last)
{
	return KL::lexicographical_compare(first0, last0, first, last,
		KL::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename Less>
inline bool lexicographical_compare(InIterL first0, InIterL last0,
									InIterR first, InIterR last, Less less)
{
	for(; first0 != last0 && first != last; ++first0, ++first)
	{
		if(less(*first0, *first)) return true;
		if(less(*first, *first0)) return false;
	}
	return !(first0 != last0 || first == last);
}
template<typename InIterL, typename InIterR>
inline int lexicographical_compare_3way(InIterL first0, InIterL last0,
										InIterR first, InIterR last)
{
	return KL::lexicographical_compare_3way(first0, last0, first, last,
		KL::less2<iterator_traits<InIterL>::type, 
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename Less>
inline int lexicographical_compare_3way(InIterL first0, InIterL last0,
										InIterR first, InIterR last, Less less)
{
	for(; first0 != last0 && first != last; ++first0, ++first)
	{
		if(less(*first0, *first)) return -1;
		if(less(*first, *first0)) return 1;
	}
	return (first0 != last0) ? 1 : ((first != last) ? -1 : 0);
}
// FUNCTION lexicographical_compare lexicographical_compare_3way}
// FUNCTION smaller, min_element, bigger, max_element {
// --- some c header has defined the macro "min" and "max".
// --- use "smaller" and "bigger" as replacements.
template<typename Type>
inline Type &smaller(Type &first, Type &second)
{	
	if(second < first) return second;
	return first;
}
template<typename Type>
inline Type &bigger(Type &first, Type &second)
{
	if(first < second) return second;
	return first;
}
template<typename Type>
inline const Type &smaller(const Type &first, const Type &second)
{
	if(second < first) return second;
	return first;
}
template<typename Type>
inline const Type &bigger(const Type &first, const Type &second)
{
	if(first < second) return second;
	return first;
}
template<typename Type, typename Less>
inline Type &smaller(Type &first, Type &second, Less less)
{
	if(less(second, first)) return second;
	return first;
}
template<typename Type, typename Less>
inline Type &bigger(Type &first, Type &second, Less less)
{
	if(less(first, second)) return second;
	return first;
}
template<typename Type, typename Less>
inline const Type &smaller(const Type &first, const Type &second, Less less)
{
	if(less(second, first)) return second;
	return first;
}
template<typename Type, typename Less>
inline const Type &bigger(const Type &first, const Type &second, Less less)
{
	if(less(first, second)) return second;
	return first;
}
template<typename InIter>
inline InIter min_element(InIter first, InIter last)
{
	if(first == last) return last;
	InIter result = first;
	while(++first != last) if(*first < *result) result = first;
	return result;
}
template<typename InIter>
inline InIter max_element(InIter first, InIter last)
{
	if(first == last) return last;
	InIter result = first;
	while(++first != last) if(*result < *first) result = first;
	return result;
}
template<typename InIter, typename Less>
inline InIter min_element(InIter first, InIter last, Less less)
{
	if(first == last) return last;
	InIter result = first;
	while(++first != last) if(less(*first, *result)) result = first;
	return result;
}
template<typename InIter, typename Less>
inline InIter max_element(InIter first, InIter last, Less less)
{
	if(first == last) return last;
	InIter result = first;
	while(++first != last) if(less(*result, *first)) result = first;
	return result;
}
// FUNCTION smaller, min_element, bigger, max_element }
// FUNCTION mismatch {
template<typename InIterL, typename InIterR>
inline KL::pair<InIterL, InIterR> mismatch(InIterL first0, InIterL last0,
											InIterR first)
{
	return mismatch(first0, last0, first,
		KL::equal_to2<iterator_traits<InIterL>::type, iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename Equal>
inline KL::pair<InIterL, InIterR> mismatch(InIterL first0, InIterL last0, 
											InIterR first, Equal fun)
{
	for(; first0 != last0; ++first0, ++first)
	{
		if(!fun(*first0, *first)) break;
	}
	return KL::pair<InIterL, InIterR>(first0, first);
}
// FUNCTION mismatch }
// FUNCTION next_permutation, prev_permutation {
template<typename BidIter>
inline bool next_permutation(BidIter first, BidIter last)
{
	return KL::next_permutation(first, last,
		KL::less<typename iterator_traits<BidIter>::type>());
}
template<typename BidIter, typename Less>
inline bool next_permutation(BidIter first, BidIter last, Less fun)
{
	if(first == last) return false;
	BidIter next = last; --next;
	if(first == next) return false;
	BidIter prev = next;
	for(; first != next;)
	{
		if(fun(*--prev, *next))
		{
			BidIter dest = last; while(!fun(*prev, *--dest));
			KL::iter_swap(prev, dest);
			KL::reverse(next, last);
			return true;
		}
		next = prev;
	}
	KL::reverse(first, last);
	return false;
}
template<typename BidIter>
inline bool prev_permutation(BidIter first, BidIter last)
{
	return KL::prev_permutation(first, last, 
		KL::less<typename iterator_traits<BidIter>::type>());
}
template<typename BidIter, typename Less>
inline bool prev_permutation(BidIter first, BidIter last, Less fun)
{
	if(first == last) return false;
	BidIter next = last; --next;
	if(first == next) return false;
	BidIter prev = next;
	for(; first != next;)
	{
		if(fun(*next, *--prev))
		{
			BidIter dest = last; while(!fun(*--dest, *prev));
			KL::iter_swap(prev, dest);
			KL::reverse(next, last);
			return true;
		}
		next = prev;
	}
	KL::reverse(first, last);
	return false;
}
// FUNCTION next_permutation, prev_.. }
// FUNCTION random_sample {
template<typename RanIter, typename RanIterDest>
inline RanIterDest random_sample(RanIter first0, RanIter last0,
								 RanIterDest d_first, RanIterDest d_last)
{
	ASSERT(false);
	do some thing here;
	return d_last;
}
template<typename RanIter, typename RanIterDest>
inline RanIterDest random_sample_n(RanIter first0, RanIter last0,
								   RanIterDest d_first, size_t num)
{
	ASSERT(false);
	do some thing here;
	return d_first + num;
}
// FUNCTION random_sample }
// FUNCTION random_shuffle {
template<typename RanIter>
inline void random_shuffle(RanIter first, RanIter last)
{
	size_t num = KL::distance(first, last);
	if(num <= 0) return;
	for(RanIter temp = first; temp != last; ++temp)
	{
		KL::iter_swap(temp, first + diff_t(::rand() % num));
	}
}
template<typename RanIter, typename Random>
inline void random_shuffle(RanIter first, RanIter last, Random rand)
{
	size_t num = KL::distance(first, last);
	if(num <= 0) return;
	for(RanIter temp = first; temp != last; ++temp)
	{
		KL::iter_swap(temp, first + diff_t(rand() % num));
	}
}
// FUNCTION random_shuffle }
// FUNCTION remove, remove_if, remove_copy, remove_copy_if {
template<typename FwdIter, typename Value>
inline FwdIter remove(FwdIter first, FwdIter last, Value const &value)
{
	while(first != last && !(*first == value)) ++first;
	if(first == last) return last;
	FwdIter dest = first;
	while(++first != last)
	{
		if(*first == value) continue;
		*dest++ = *first;
	}
	return dest;
}
template<typename FwdIter, typename Bool>
inline FwdIter remove_if(FwdIter first, FwdIter last, Bool fun)
{
	while(first != last && !fun(*first)) ++first;
	if(first == last) return last;
	FwdIter dest = first;
	while(++first != last)
	{
		if(fun(*first)) continue;
		*dest++ = *first;
	}
	return dest;
}
template<typename FwdIter, typename FwdIterDest, typename Value>
inline FwdIterDest remove_copy(FwdIter first, FwdIter last, FwdIterDest result, Value const &value)
{
	for(; first != last; ++first)
	{
		if(*first == value) continue;
		*result++ = *first;
	}
	return result;
}
template<typename FwdIter, typename FwdIterDest, typename Bool>
inline FwdIterDest remove_copy_if(FwdIter first, FwdIter last, FwdIterDest result, Bool fun)
{
	for(; first != last; ++first)
	{
		if(fun(*first)) continue;
		*result++ = *first;
	}
	return result;
}
// FUNCTION remove, remove_if, remove_copy, remove_copy_if }
// FUNCTION replace, replace_if, replace_copy, replace_copy_if {
template<typename FwdIter, typename Value>
inline void replace(FwdIter first, FwdIter last, 
					Value const &old_value, Value const &new_value)
{
	for(; first != last; ++first) if(*first == old_value) *first = new_value;
}
template<typename FwdIter, typename Bool, typename Value>
inline void replace_if(FwdIter first, FwdIter last, Bool fun, Value const &new_value)
{
	for(; first != last; ++first) if(fun(*first)) *first = new_value;
}
template<typename FwdIter, typename FwdIterDest, typename Value>
inline void replace_copy(FwdIter first, FwdIter last, FwdIterDest result, 
						 Value const &old_value, Value const &new_value)
{
	for(; first != last; ++first, ++result) 
	{
		if(*first == old_value) *result = new_value;
		else *result = *first;
	}
}
template<typename FwdIter, typename FwdIterDest, typename Bool, typename Value>
inline void replace_copy_if(FwdIter first, FwdIter last, FwdIterDest result,
							Bool fun, Value const &new_value)
{
	for(; first != last; ++first, ++result) 
	{
		if(fun(*first)) *result = new_value;
		else *result = *first;
	}
}
// FUNCTION replace, replace_if, replace_copy, replace_copy_if }
// FUNCTION reverse, reverse_copy {
template<typename BidIter>
inline void reverse(BidIter first, BidIter last)//, KL::bidirectional_iterator_tag)
{
	for(; first != last && first != --last; ++first) 
	{
		KL::iter_swap(first, last);
	}
}
template<typename BidIter, typename FwdIter>
inline FwdIter reverse_copy(BidIter first, BidIter last, FwdIter result)
{
	while(first != last) *result++ = *--last;
	return result;
}
// FUNCTION reverse, reverse_copy }
// FUNCTION rotate_copy {
template<typename FwdIter>
inline FwdIter rotate(FwdIter first, FwdIter mid, FwdIter last)
{
	if(first == mid) return last;
	if(mid == last) return first;
	typedef iterator_traits<FwdIter>::type type;
	typedef KL::_memory_helper_<type> _helper;
	size_t num1 = KL::distance(first, mid);
	size_t num2 = KL::distance(mid, last);
	if(num1 <= num2)
	{
		KL::raw_buffer<type> buf(num1);
		_helper::raw_copy_n(first, num1, buf.begin());
		first = copy_n(mid, num2, first);
		copy_n(buf.begin(), buf.size(), first);
		_helper::destroy_n(buf.begin(), num1);
	}
	else
	{
		KL::raw_buffer<type> buf(num1);
		_helper::raw_copy_n(first, num2, buf.begin());
		first = KL::copy_n(mid, num2, first);
		KL::copy_backward(first, mid, last);
		KL::copy_n(buf.begin(), buf.size(), first);
		_helper::destroy_n(buf.begin(), num2);
	}
	return first;
}
template<typename InIter, typename OutIter>
inline OutIter rotate_copy(InIter first, InIter mid, InIter last, OutIter dest)
{
	dest = KL::copy(mid, last, dest);
	KL::copy(first, mid, dest);
	return dest;
}
// FUNCTION rotate_copy }
// FUNCTION search, search_n {
template<typename InIterSrc, typename InIterDest>
inline InIterSrc search(InIterSrc first0, InIterSrc last0, 
						InIterDest first, InIterDest last)
{
	return KL::search(first0, last0, first, last, 
		KL::equal_to2<iterator_traits<InIterSrc>::type, 
		iterator_traits<InIterDest>::type>());
}
template<typename InIterSrc, typename InIterDest, typename Equal>
inline InIterSrc search(InIterSrc first0, InIterSrc last0, 
						InIterDest first, InIterDest last, Equal fun)
{
	size_t obj_num = KL::distance(first, last);
	if(obj_num == 0) return first0;
	size_t src_num = KL::distance(first0, last0);
	for(; src_num >= obj_num; ++first0, --src_num)
	{
		InIterSrc src = first0;
		InIterDest head = first;
		size_t num = obj_num;
		for(; num && fun(*src, *head); ++head, ++src, --num);
		if(!num) return first0;
	}
	return last0;
}
template<typename InIterSrc, typename InIterDest>
inline InIterSrc search_end(InIterSrc first0, InIterSrc last0, 
							InIterDest first, InIterDest last)
{
	return KL::search_end(first0, last0, first, last, 
		KL::equal_to2<iterator_traits<InIterSrc>::type, 
		iterator_traits<InIterDest>::type>());
}
template<typename InIterSrc, typename InIterDest, typename Equal>
inline InIterSrc search_end(InIterSrc first0, InIterSrc last0, 
							InIterDest first, InIterDest last, Equal fun)
{
	return KL::_search_end_(first0, last0, first, last, fun,
		KL::iterator_category(first0), KL::iterator_category(first));
}
template<typename InIterSrc, typename InIterDest, typename Equal>
inline InIterSrc _search_end_(InIterSrc first0, InIterSrc last0, 
							  InIterDest first, InIterDest last, Equal fun,
							  KL::input_iterator_tag *,
							  KL::input_iterator_tag *)
{
	size_t obj_num = KL::distance(first, last);
	if(obj_num == 0) return first0;
	InIterSrc result = last0;
	size_t src_num = KL::distance(first0, last0);
	for(; src_num >= obj_num; ++first0, --src_num)
	{
		InIterSrc src = first0;
		InIterDest head = first;
		size_t num = obj_num;
		for(; num && fun(*src, *head); ++head, ++src, --num);
		if(!num) result = first0;
	}
	return result;
}
template<typename BidIterSrc, typename BidIterDest, typename Equal>
inline BidIterSrc _search_end_(BidIterSrc first0, BidIterSrc last0, 
							   BidIterDest first, BidIterDest last, Equal fun, 
							   KL::bidirectional_iterator_tag *,
							   KL::bidirectional_iterator_tag *)
{
	size_t obj_num = KL::distance(first, last);
	if(obj_num == 0) return first0;
	size_t src_num = KL::distance(first0, last0);
	for(first0 = last0; src_num >= obj_num; --first0, --src_num)
	{
		BidIterSrc src = first0;
		size_t num = obj_num;
		for(first = last; num && fun(*--src, *--first); --num);
		if(!num) return src;
	}
	return last0;
}
template<typename InIterSrc, typename Value>
inline InIterSrc search_n(InIterSrc first0, InIterSrc last0, 
						  size_t num, Value const &value)
{
	return search_n(first0, last0, num, value, 
		KL::equal_to2<iterator_traits<InIterSrc>::type, Value>());
}
template<typename InIterSrc, typename Value, typename Equal>
inline InIterSrc search_n(InIterSrc first0, InIterSrc last0, 
						  size_t num, Value const &value, Equal fun)
{
	return KL::_search_n_(first0, last0, num, value, fun,
		KL::iterator_category(first0));
}
template<typename InIterSrc, typename Value, typename Equal>
inline InIterSrc _search_n_(InIterSrc first0, InIterSrc last0, 
							size_t num, Value const &value, Equal &fun,
							KL::random_access_iterator_tag *)
{
	if(num == 0) return first0;
	size_t src_num = KL::distance(first0, last0);
	size_t off = 0;
	while(src_num >= num)
	{		
		InIterSrc tail = first0 + num;
		size_t off2 = 0;
		while(fun(*--tail, value))
		{
			if(off + (++off2) == num) return first0;
		}
		first0 = ++tail;
		off = off2;
		src_num -= num - off2;
	}
	return last0;
}
template<typename InIterSrc, typename Value, typename Equal>
inline InIterSrc _search_n_(InIterSrc first0, InIterSrc last0, 
							size_t num, Value const &value, Equal &fun,
							KL::input_iterator_tag *)
{
	if(num == 0) return first0;
	while(first0 != last0)
	{
		if(fun(*first0, value))
		{
			size_t count = num;
			InIterSrc result = first0;
			do {
				if(--count == 0) return result;
			} while(first0 != last0 && fun(*++first0, value));
		}
		else ++first0;
	}
	return last0;
}
// FUNCTION search, search_n }
// FUNCTION set_difference, set_symmetric_difference, set_intersection, set_union {
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter set_difference(InIterL first0, InIterL last0, 
							  InIterR first, InIterR last, OutIter result)
{
	return KL::set_difference(first0, last0, first, last, result,
		KL::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter set_difference(InIterL first0, InIterL last0, 
							  InIterR first, InIterR last, 
							  OutIter result, Less fun)
{
	while(first0 != last0 && first != last)
	{
		if(fun(*first0, *first)) *result = *first0, ++result, ++first0; 
		else if(fun(*first, *first0)) ++first;
		else ++first0, ++first;
	}
	return KL::copy(first0, last0, result);
}
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter set_symmetric_difference(InIterL first0, InIterL last0,
										InIterR first, InIterR last, 	OutIter result)
{
	return KL::set_symmetric_difference(first0, last0, first, last, result,
		KL::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter set_symmetric_difference(InIterL first0, InIterL last0, 
										InIterR first, InIterR last, 
										OutIter result, Less fun)
{
	while(first0 != last0 && first != last)
	{
		if(fun(*first0, *first)) *result = *first0, ++result, ++first0; 
		else if(fun(*first, *first0)) *result = *first, ++result, ++first;
		else ++first0, ++first;
	}
	result = KL::copy(first0, last0, result);
	return KL::copy(first, last, result);
}
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter set_intersection(InIterL first0, InIterL last0,
								InIterR first, InIterR last, 	OutIter result)
{
	return KL::set_intersection(first0, last0, first, last, result,
		KL::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter set_intersection(InIterL first0, InIterL last0, 
								InIterR first, InIterR last, 
								OutIter result, Less fun)
{
	while(first0 != last0 && first != last)
	{
		if(fun(*first0, *first)) ++first0; 
		else if(fun(*first, *first0)) ++first;
		else *result = *first, ++first0, ++first, ++result;
	}
	return result;
}
template<typename InIterL, typename InIterR, typename OutIter>
inline OutIter set_union(InIterL first0, InIterL last0,
						 InIterR first, InIterR last, 	OutIter result)
{
	return KL::set_union(first0, last0, first, last, result,
		KL::less2<iterator_traits<InIterL>::type,
		iterator_traits<InIterR>::type>());
}
template<typename InIterL, typename InIterR, typename OutIter, typename Less>
inline OutIter set_union(InIterL first0, InIterL last0, 
						 InIterR first, InIterR last, 
						 OutIter result, Less fun)
{
	while(first0 != last0 && first != last)
	{
		if(fun(*first0, *first)) *result = *first0, ++first0, ++result; 
		else if(fun(*first, *first0)) *result = *first, ++first, ++result;
		else *result = *first, ++first0, ++first, ++result;
	}
	result = KL::copy(first0, last0, result);
	return KL::copy(first, last, result);
}
// FUNCTION set_difference, set_symmetric_difference, set_intersection, set_union }
// FUNCTION swap_ranges {
template<typename FwdIterL, typename FwdIterR>
inline FwdIterR swap_ranges(FwdIterL first0, FwdIterL last0, FwdIterR first)
{
	for(; first0 != last0; ++first0, ++first) KL::iter_swap(first0, first);
	return first;
}
// FUNCTION swap_ranges }
// FUNCTION transform {
template<typename InIter, typename OutIter, typename Func1>
inline OutIter transform(InIter first, InIter last, OutIter result, Func1 fun)
{
	for(; first != last; ++first, ++result) *result = fun(*first);
	return result;
}
template<typename InIterL, typename InIterR, typename OutIter, typename Func1>
inline OutIter transform(InIterL first0, InIterL last0,
						 InIterR first, OutIter result, Func1 fun)
{
	for(; first0 != last0; ++first, +first0, ++result)
		*result = fun(*first0, *first);
	return result;
}
// FUNCTION transform }
// FUNCTION unique, unique_copy {
template<typename FwdIter, typename Equal>
inline FwdIter unique(FwdIter first, FwdIter last, Equal fun)
{
	if(first == last) return last;
	FwdIter temp = first;
	while (++first != last && !fun(*first, *temp)) temp = first;
	if(first == last) return last;
	while (++first != last) if(!fun(*first, *temp)) *++temp = *first;
	return ++temp;
}
template<typename FwdIter>
inline FwdIter unique(FwdIter first, FwdIter last)
{
	return unique(first, last,
		KL::equal_to<KL::iterator_traits<FwdIter>::type>());
}
template<typename FwdIter, typename OutIter, typename Equal>
inline FwdIter unique_copy(FwdIter first, FwdIter last,
						   OutIter result, Equal fun)
{
	if(first == last) return result;
	*result = *first;
	while (++first != last) if(!fun(*first, *result)) *++result = *first;
	return ++result;
}
template<typename FwdIter, typename OutIter>
inline FwdIter unique_copy(FwdIter first, FwdIter last, OutIter result)
{
	return unique_copy(first, last, result,
		KL::equal_to<KL::iterator_traits<FwdIter>::type>());
}
// FUNCTION unique, unique_copy }
KL_END

#endif // __STD_ALGORITHM_H_VERSION_KL__
/********************* resume **********************

// numeric.
KL::accumulate
KL::adjacent_difference
KL::inner_product
KL::iota
KL::partial_sum
KL::power

// find.
KL::adjacent_find
KL::count KL::count_if
KL::find KL::find_if KL::find_first_of KL::find_end
KL::mismatch
KL::search (KL::search_end) KL::search_n

// compare.
KL::equal
KL::lexicographical_compare
KL::lexicographical_compare_3way
KL::smaller KL::min_element
KL::bigger KL::max_element

// move data.
KL::copy KL::copy_n KL::copy_backward
KL::fill KL::fill_n
KL::iter_swap
KL::next_permutation KL::prev_permutation
KL::random_shuffle KL::random_sample(X) KL::random_sample_n(X)
KL::remove KL::remove_copy KL::remove_if KL::remove_copy_if
KL::replace KL::replace_copy KL::remove_if KL::replace_copy_if
KL::swap KL::swap_ranges
KL::unique KL::unique_copy

// set.
KL::includes
KL::set_difference
KL::set_intersection
KL::set_symmetric_difference
KL::set_union

// apply function.
KL::foreach
KL::generate KL::generate_n
KL::transform

// sort.
KL::is_heap
KL::push_heap KL::pop_heap
KL::make_heap KL::sort_heap
KL::nth_element
KL::partial_sort KL::partial_sort_copy
KL::partition KL::stable_partition
KL::sort KL::stable_sort
KL::merge KL::inplace_merge

// binary
KL::binary_search
KL::equal_range
KL::lower_bound
KL::upper_bound

********************* resume **********************/
